/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package Source.Utils;

/**
 *
 * @author Dani
 */
public class StationSort {
    
    private int[] numbers;
    private int[] helper;

    private int number;

    public void Sort(int[] values) {
        this.numbers = values;
        number = values.length;
        this.helper = new int[number];
        Mergesort(0, number - 1);
    }

    private void Mergesort(int low, int high) {
        // Check if low is smaller then high, if not then the array is sorted
        if (low < high) {
            // Get the index of the element which is in the middle
            int middle = (low + high) / 2;
            // Sort the left side of the array
            Mergesort(low, middle);
            // Sort the right side of the array
            Mergesort(middle + 1, high);
            // Combine them both
            Merge(low, middle, high);
        }
    }

    private void Merge(int low, int middle, int high) {

        // Copy both parts into the helper array
        for (int i = low; i <= high; i++) {
                helper[i] = numbers[i];
        }

        int i = low;
        int j = middle + 1;
        int k = low;

        // Copy the smallest values from either the left or the right side back
        // to the original array
        while (i <= middle && j <= high) {
            if (helper[i] <= helper[j]) {
                    numbers[k] = helper[i];
                    i++;
            } else {
                    numbers[k] = helper[j];
                    j++;
            }
            k++;
        }

        // Copy the rest of the left side of the array into the target array
        while (i <= middle) {
            numbers[k] = helper[i];
            k++;
            i++;
        }
    }
}
